package _go

import "math"

/*188. 买卖股票的最佳时机 IV
难度
困难

611

收藏

分享
切换为英文
接收动态
反馈
给定一个整数数组 prices ，它的第 i 个元素 prices[i] 是一支给定的股票在第 i 天的价格。

设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。

注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。



示例 1：

输入：k = 2, prices = [2,4,1]
输出：2
解释：在第 1 天 (股票价格 = 2) 的时候买入，在第 2 天 (股票价格 = 4) 的时候卖出，这笔交易所能获得利润 = 4-2 = 2 。
示例 2：

输入：k = 2, prices = [3,2,6,5,0,3]
输出：7
解释：在第 2 天 (股票价格 = 2) 的时候买入，在第 3 天 (股票价格 = 6) 的时候卖出, 这笔交易所能获得利润 = 6-2 = 4 。
     随后，在第 5 天 (股票价格 = 0) 的时候买入，在第 6 天 (股票价格 = 3) 的时候卖出, 这笔交易所能获得利润 = 3-0 = 3 。


提示：

0 <= k <= 100
0 <= prices.length <= 1000
0 <= prices[i] <= 1000
*/

func maxProfit(k int, prices []int) int {
	if k == 0 || len(prices) < 2 {
		return 0
	}
	n := len(prices)
	k = min(k, n/2) //最多就能交易这么多次 因为买卖需要两次交易
	//第i天第k次 买入收益最大
	buy := make([][]int, len(prices))
	//第i天地k次卖出收益最大
	sell := make([][]int, len(prices))

	for i := range buy {
		buy[i] = make([]int, k+1)
		sell[i] = make([]int, k+1)
	}

	//初始化数组
	buy[0][0] = -prices[0]

	for i := 1; i <= k; i++ {
		buy[0][i] = math.MinInt64 / 2
		sell[0][i] = math.MinInt64 / 2
	}
	//从1开始遍历
	for i := 1; i < len(prices); i++ {
		//先从买入开始计算
		buy[i][0] = max(buy[i-1][0], sell[i-1][0]-prices[i])
		//循环遍历 后天的天数
		for j := 1; j <= k; j++ {
			buy[i][j] = max(buy[i-1][j], sell[i-1][j]-prices[i])
			//这个地方要注意  是前一天的前一次买入 加上今天的股价
			sell[i][j] = max(sell[i-1][j], buy[i-1][j-1]+prices[i])
		}
	}
	return max(sell[n-1]...)
}

func min(a, b int) int {
	if a > b {
		return b
	}
	return a
}

func max(a ...int) int {
	res := a[0]
	for _, v := range a[1:] {
		if v > res {
			res = v
		}
	}
	return res
}
